SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Recursive tree</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Recursive tree</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

<p>In <a href="Graph_theory" title="Graph theory">graph theory</a>, a <b>recursive tree</b> (i.e., unordered tree) is a <a href="Graph_labeling" title="Graph labeling">labeled</a>, rooted <a href="Tree_(graph_theory)" title="Tree (graph theory)">tree</a>. A size-<span class="texhtml mvar" style="font-style:italic;">n</span> recursive tree's <a href="Vertex_(graph_theory)" title="Vertex (graph theory)">vertices</a> are labeled by distinct <a href="Positive_integer" class="mw-redirect" title="Positive integer">positive integers</a> <span class="texhtml">1, 2, …, <i>n</i></span>, where the labels are strictly increasing starting at the root labeled 1. Recursive trees are <a href="Planar_graph" title="Planar graph">non-planar</a>, which means that the children of a particular vertex are not ordered; for example, the following two size-3 recursive trees are equivalent: <span class="texhtml"><sub>3</sub>/<sup>1</sup>\<sub>2</sub> = <sub>2</sub>/<sup>1</sup>\<sub>3</sub></span>.

</p><p>Recursive trees also appear in literature under the name <i>Increasing Cayley trees</i>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Properties">Properties</h2></div>

<p>The number of size-<i>n</i> recursive trees is given by

</p>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{n}=(n-1)!.\,}</annotation>

</semantics>

</math></span><img src="./13c5b835b138d4aa7182ec5ef24713581096d464.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.562ex; height:2.843ex;" alt="{\displaystyle T_{n}=(n-1)!.\,}" loading="lazy"></span></dd></dl>

<p>Hence the exponential <a href="Generating_function" title="Generating function">generating function</a> <i>T</i>(<i>z</i>) of the sequence <i>T</i><sub><i>n</i></sub> is given by

</p>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<mfrac>

<msup>

</mrow>

</msup>

<mrow>

</mrow>

</mfrac>

</mrow>

<mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T(z)=\sum _{n\geq 1}T_{n}{\frac {z^{n}}{n!}}=\log \left({\frac {1}{1-z}}\right).}</annotation>

</semantics>

</math></span><img src="./544984f32b923cbf1307da2859aba6b3cc66cfd8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:33.161ex; height:6.843ex;" alt="{\displaystyle T(z)=\sum _{n\geq 1}T_{n}{\frac {z^{n}}{n!}}=\log \left({\frac {1}{1-z}}\right).}" loading="lazy"></span></dd></dl>

<p>Combinatorically, a recursive tree can be interpreted as a root followed by an unordered sequence of recursive trees. Let <i>F</i> denote the family of recursive trees. Then

</p>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F=\circ +{\frac {1}{1!}}\cdot \circ \times F+{\frac {1}{2!}}\cdot \circ \times F*F+{\frac {1}{3!}}\cdot \circ \times F*F*F*\cdots =\circ \times \exp(F),}</annotation>

</semantics>

</math></span><img src="./9f351d0804e68d4c13ad981e98049311ecda77c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:76.302ex; height:5.343ex;" alt="{\displaystyle F=\circ +{\frac {1}{1!}}\cdot \circ \times F+{\frac {1}{2!}}\cdot \circ \times F*F+{\frac {1}{3!}}\cdot \circ \times F*F*F*\cdots =\circ \times \exp(F),}" loading="lazy"></span></dd></dl>

<p>where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \circ }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \circ }</annotation>

</semantics>

</math></span><img src="./99add39d2b681e2de7ff62422c32704a05c7ec31.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: 0.125ex; margin-bottom: -0.297ex; width:1.162ex; height:1.509ex;" alt="{\displaystyle \circ }" loading="lazy"></span> denotes the node labeled by 1, × the <a href="Cartesian_product" title="Cartesian product">Cartesian product</a> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle *}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle *}</annotation>

</semantics>

</math></span><img src="./8e9972f426d9e07855984f73ee195a21dbc21755.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: 0.079ex; margin-bottom: -0.25ex; width:1.162ex; height:1.509ex;" alt="{\displaystyle *}" loading="lazy"></span> the partition product for labeled objects.

</p><p>By translation of the formal description one obtains the <a href="Differential_equation" title="Differential equation">differential equation</a> for <i>T</i>(<i>z</i>)

</p>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T'(z)=\exp(T(z)),}</annotation>

</semantics>

</math></span><img src="./a65b91232fb49875baac83bbcb8cae63a6642a7e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.943ex; height:3.009ex;" alt="{\displaystyle T'(z)=\exp(T(z)),}" loading="lazy"></span></dd></dl>

<p>with <i>T</i>(0) = 0.

</p>

<div class="mw-heading mw-heading2"><h2 id="Bijections">Bijections</h2></div>

<p>There are <a href="Bijection" title="Bijection">bijective</a> correspondences between recursive trees of size <i>n</i> and <a href="Permutation" title="Permutation">permutations</a> of size <i>n</i> − 1.

</p>

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

<p>Recursive trees can be generated using a simple <a href="Stochastic_process" title="Stochastic process">stochastic process</a>. Such <a href="Random_recursive_tree" title="Random recursive tree">random recursive trees</a> are used as simple models for epidemics.

</p>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li><i><a href="Analytic_Combinatorics" class="mw-redirect" title="Analytic Combinatorics">Analytic Combinatorics</a></i>, Philippe Flajolet and Robert Sedgewick, Cambridge University Press, 2008.</li>

<li><i>Varieties of Increasing Trees</i>, Francois Bergeron, Philippe Flajolet, and Bruno Salvy. In Proceedings of the 17th Colloquium on Trees in Algebra and Programming, Rennes, France, February 1992. Proceedings published in Lecture Notes in Computer Science vol. 581, J.-C. Raoult Ed., 1992, pp. 24–48.</li>

<li><i>Profile of random trees: correlation and width of random recursive trees and binary search trees</i>, Michael Drmota and Hsien-Kuei Hwang, Adv. Appl. Prob., 37, 1–21, 2005.</li>

<li><i>Profiles of random trees: Limit theorems for random recursive trees and binary search trees</i>, Michael Fuchs, Hsien-Kuei Hwang, Ralph Neininger., Algorithmica, 46, 367–407, 2006.</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-04-16" href="https://en.wikipedia.org/wiki/?title=Recursive_tree&oldid=1285922157">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>